package com.beney.al.string;

public class Kmp {
    private Kmp() {
    }

    private static int[] getNext(char[] chs) {
        int len = chs.length, dump = 0;
        int[] next = new int[len];  // next[i]存储[0..i-1]最长匹配前后缀长度
        for (int i = 2; i < len; ++i) {
            while (dump > 0 && chs[i - 1] != chs[dump]) {
                dump = next[dump];
            }
            if (chs[dump] == chs[i - 1]) {
                dump++;
            }
            next[i] = dump;
        }
        return next;
    }


    /**
     * @param src 文本串
     * @param tmp 模板串
     * @return tmp在src中第一次出现的位置，若不存在则返回{@code -1}
     */
    public static int getIndex(String src, String tmp) {
        int lenS, lenT;
        if ((lenS = src.length()) < (lenT = tmp.length()))
            return -1;
        char[] s = src.toCharArray(),
                t = tmp.toCharArray();
        int[] next = getNext(t);
        int dump = 0;
        for (int i = 0; i < lenS; ++i) {
            while (dump > 0 && t[dump] != s[i]) {
                dump = next[dump];
            }
            if (t[dump] == s[i]) {
                dump += 1;
                if (dump == lenT) { // 匹配成功
                    return i - lenT + 1;
                }
            }
        }
        return -1;
    }
}
